class Solution {
    public int[] sortArray(int[] nums) {
        merge_sort(nums, 0, nums.length-1);
        return nums;
    }

    private void merge_sort(int[] nums, int start, int end) {
        // 递归的结束条件：只剩下一个元素
        if (start >= end) {
            return;
        }
        // 先分解左子树、再分解右子树
        int mid = (start+end) / 2;
        merge_sort(nums, start, mid);
        merge_sort(nums, mid+1, end);
        // 最后将两者合并
        merge(nums, start, mid, end);
    }

    // 合并两个有序数组的操作
    private void merge(int[] nums, int start, int mid, int end) {
        int s1 = start, e1 = mid, s2 = mid+1, e2 = end;
        // 借助辅助数组
        int[] array = new int[end-start+1];
        int k = 0;
        while (s1 <= e1 && s2 <= e2) {
            if (nums[s1] < nums[s2]) {
                array[k++] = nums[s1++];
            } else {
                array[k++] = nums[s2++];
            }
        }
        while (s1 <= e1) {
            array[k++] = nums[s1++];
        }
        while (s2 <= e2) {
            array[k++] = nums[s2++];
        }
        // 开始存放到原始数组中
        // 从start开始的，总共有K个元素
        for (int i = start; i < start+k; i++) { // 也可以直接写为end
            nums[i] = array[i-start];
        }
    }
}